// 实现⼀个算法，⽤于实现最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元。要求：输⼊是⾦额，输出最少的找零纸币数。⽐如输⼊24，输出最⼩找零纸币数：3(⼀张20元、两张2元)。(20)
// 输⼊：24
// 输出：3
pub fn dp_rec_mc(amount: u32) -> u32 {
    let coins = vec![1, 2, 5, 10, 20, 30, 50, 100];
    let mut dp = vec![0; amount as usize + 1];
    for i in 1..amount + 1 {
        dp[i as usize] = i;
        for &coin in &coins {
            if i >= coin {
                dp[i as usize] = dp[i as usize].min(dp[(i - coin) as usize] + 1);
            }
        }
    }
    dp[amount as usize]
}
